package sword_offer;

import java.util.PriorityQueue;

/**
 * @ClassName _40getLeastNumbers
 * @Description: 输入整数数组 arr ，找出其中最小的 k 个数。例如，输入4、5、1、6、2、7、3、8这8个数字，则最小的4个数字是1、2、3、4。
 *
 *  
 *
 * 示例 1：
 *
 * 输入：arr = [3,2,1], k = 2
 * 输出：[1,2] 或者 [2,1]
 * 示例 2：
 *
 * 输入：arr = [0,1,2,1], k = 1
 * 输出：[0]
 *  
 *
 * 限制：
 *
 * 0 <= k <= arr.length <= 10000
 * 0 <= arr[i] <= 10000
 *
 * 来源：力扣（LeetCode）
 * 链接：https://leetcode.cn/problems/zui-xiao-de-kge-shu-lcof
 * 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
 * @Author: yongliang.ma
 * @Create_time:2022/10/11 19:14
 */
public class _40getLeastNumbers {

    public static void main(String[] args) {

        int[] arr = new int[]{0,0,0,2,0,5};
        int[] leastNumbers = new _40getLeastNumbers().getLeastNumbers(arr, 0);
        System.out.println(2);
    }


    // 返回的是数字的位置
    public int[] getLeastNumbers(int[] arr, int k) {
        int[] res = new int[k];
        PriorityQueue<Integer> priorityQueue = new PriorityQueue<>(k, (a, b) -> b - a);
        if (k == 0) { // 排除 0 的情况
            return res;
        }
        for (int i = 0; i < k; i++) {
            priorityQueue.offer(arr[i]);
        }
        for (int i = k; i < arr.length; i++) {
            if (priorityQueue.peek() > arr[i]){
                priorityQueue.poll();
                priorityQueue.offer(arr[i]);
            }
        }

        for (int i = 0; i < k; i++) {
            res[i] = priorityQueue.poll() ;
        }
        return res;
    }

}
